package org.zhs.tree;


import java.util.NoSuchElementException;

/**
 * @Author: zhs
 * @Date: 2024/5/7 21:27
 * @Version: 1.0
 * @Description: 二叉查询树
 * <p>
 * 对于 insert 、 remove 、 以及查找方法来说其实就是不断的递归到满足条件为止（包括终止条件）。
 * 对于二叉查询树来说，每个节点可以拥有至多两个子节点。
 * 左侧子节点存放比自己小的数据， 右侧子节点存放比自己大的数据。
 * <p>
 * 这样来说的话，在最优的情况的下它的深度为 logN(子节点均匀的分布在每个根节点), 在最坏的情况下它的深度为 n（子节点分布在一侧，其实已经坍缩成一个线性表了）
 *
 *
 * (1)前序遍历:可以用来实现目录结构的显示。
 * (2)中序遍历:可以用来做表达式树，在编译器底层实现的时候用户可以实现基本的加减乘除，比如 a*b+c。
 * (3)后序遍历可以用来实现计算日录内的文件占用的数据大小~非常有用。
 */
public class MyBinarySearchTree<E extends Comparable<? super E>> {

    /**
     * 根节点
     */
    private TreeNode<E> root;

    public MyBinarySearchTree() {
        this.root = null;
    }

    public void makeEmpty() {
        this.root = null;
    }

    public boolean isEmpty() {
        return this.root == null;
    }

    public void insert(E data) {
        root = insert(data, root);
    }

    /**
     * 添加子节点的方法（是一个递归的方法）
     *
     * @param data
     * @param node
     * @return
     */
    private TreeNode<E> insert(E data, TreeNode<E> node) {
        if (node == null)
            return new TreeNode<>(data, null, null);

        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            node.leftNode = insert(data, node.leftNode);
        } else if (compareResult > 0) {
            node.rightNode = insert(data, node.rightNode);
        } else {
            // 重复的数据
        }
        return node;
    }


    public boolean contains(E data) {
        return contains(data, root);
    }


    /**
     * 判断树中是否包含指定的数据
     *
     * @param data
     * @param node
     * @return
     */
    private boolean contains(E data, TreeNode<E> node) {
        // 当前节点为空时返回false
        if (node == null) {
            return false;
        }

        // 传入的值和当前节点的值进行对比，判断是否相等还是从左侧或者右侧开始进行 递归
        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            return contains(data, node.leftNode);
        } else if (compareResult > 0) {
            return contains(data, node.rightNode);
        } else {
            return true;
        }
    }


    public E findMin() {
        return findMin(root).data;
    }

    /**
     * 查找最小的节点
     *
     * @param node
     * @return
     */
    private TreeNode<E> findMin(TreeNode<E> node) {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        // 递归查询左侧节点
        if (node.leftNode != null) {
            return findMin(node.leftNode);
        }
        return node;
    }

    public E findMax() {
        return findMax(root).data;
    }

    /**
     * 查找最大的节点
     *
     * @param node
     * @return
     */
    private TreeNode<E> findMax(TreeNode<E> node) {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        // 递归查询右侧节点
        if (node.rightNode != null) {
            return findMax(node.rightNode);
        }
        return node;
    }


    public void remove(E data) {
        root = remove(data, root);
    }


    /**
     * 删除节点
     * 删除操作，通常来讲是取右子树中最小的值（也可以取左子树中最大的值）来替换删除的节点的值。
     * 删除的步骤：
     * 设传入的值为 x， 找到的对应节点为 x_node
     * 1.传入要删除的值 x
     * 2.x与当前节点的值对比，小于节点的值就继续查询该节点左侧子树。大于节点的值就继续查询该节点右侧的子树。
     * 3.如果 x 与当前节点的值相等，如果 x_node 只有1个叶子节点，那么直接将 x_node 设置成为这个子节点(不需要管该子节点是否还有子节点)
     * 4.如果 x 与当前节点的值相等，并且 x_node 有2个子节点。
     *  4.1.找到 x_node 右侧子节点中最小的那个节点，并且用它的值覆盖掉 x_node 的值（注意是覆盖掉了值，没有覆盖该节点的子节点引用）。
     *  4.2.然后传入 找到的最小值 继续递归删除 x_node 的右侧子节点 （*******************************************）
     *  4.3.在上一个步骤中，为什么还要继续递归删除并且传入 找到的右侧子树最小的值继续递归删除呢？ 因为它可能还会有右子节点，
     *      那么我们只能将值覆盖到 x_node 中，因为我们还需要处理它的子节点。所以将它的值传入递归方法中继续递归查询，以此类推，一直到它的子节点全部处理完
     *
     * @param data
     * @param node
     * @return
     */
    private TreeNode<E> remove(E data, TreeNode<E> node) {
        // 如果节点是空直接返回
        if(node == null){
            return null;
        }

        // 然后要删除的值与当前节点的值进行对比
        int compareResult = data.compareTo(node.data);


        if(compareResult < 0){
            // 如果比当前节点的值小，继续从左侧查找数据，直到找到对应的数据
            node.leftNode = remove(data, node.leftNode);
        }else if(compareResult > 0){
            // 如果比当前节点的值大，继续从右侧查找数据，直到找到对应的数据
            node.rightNode = remove(data, node.rightNode);
        }else if(node.leftNode != null && node.rightNode != null){
            // 如果与当前节点的值相等，并且找到的节点还有2个子节点
            // 那么就将找到的节点的值设置为 当前节点的右侧最小节点的值
            // 然后依次递归处理找到节点的子节点(表现上看这里还是从当前节点开始递归，实际上因为传入的值是找到节点的值，所以是从找到节点开始处理)
            node.data = findMin(node.rightNode).data;
            node.rightNode = remove(node.data, node.rightNode);
        }else{
            //如果 传入的数据 与 当前节点的值相等，并且 只有一个叶子节点 ，那么直接将当前节点设置成为这个子节点(不需要管该子节点是否还有子节点)
            node = node.leftNode != null ? node.leftNode : node.rightNode;
        }

        return node;
    }


    public void prePrint(){
        prePrint(root);
    }

    /**
     * 前序遍历
     * 根 -> 左 -> 右
     * 先输出父节点、再遍历左侧子节点和右侧子节点
     * @param node
     */
    private void prePrint(TreeNode<E> node){
        // 先输出根节点
        if(node != null){
            System.out.println(node.data);
        }
        // 左侧子节点不为空，则继续递归
        if(node.leftNode != null){
            prePrint(node.leftNode);
        }
        // 右侧子节点不为空，则继续递归
        if(node.rightNode != null){
            prePrint(node.rightNode);
        }
    }


    public void midPrint(){
        midPrint(root);
    }

    /**
     * 中序遍历
     * 左 -> 根 -> 右
     * 先遍历左侧子节点、再当前节点、再遍历右侧子节点
     * @param node
     */
    private void midPrint(TreeNode<E> node){
        if(node == null){
            return;
        }
        // 先递归左侧子节点
        if(node.leftNode != null){
            midPrint(node.leftNode);
        }

        // 然后输出当前节点
        System.out.println(node.data);

        // 再递归右侧子节点
        if(node.rightNode != null){
            midPrint(node.rightNode);
        }
    }



    public void postPrint(){
        postPrint(root);
    }

    /**
     * 后序遍历
     * 左 -> 右 -> 根
     * 先遍历左侧子节点、再遍历右侧子节点 、再当前节点
     * @param node
     */
    private void postPrint(TreeNode<E> node){
        if(node == null){
            return;
        }
        // 先递归左侧子节点
        if(node.leftNode != null){
            midPrint(node.leftNode);
        }

        // 再递归右侧子节点
        if(node.rightNode != null){
            midPrint(node.rightNode);
        }

        // 然后输出当前节点
        System.out.println(node.data);
    }


    /**
     * 树的节点
     *
     * @param <E>
     */
    private static class TreeNode<E> {
        /**
         * 数据
         */
        E data;

        /**
         * 左边节点
         */
        TreeNode<E> leftNode;

        /**
         * 右边节点
         */
        TreeNode<E> rightNode;

        public TreeNode(E data) {
            this(data, null, null);
        }

        public TreeNode(E data, TreeNode<E> leftNode, TreeNode<E> rightNode) {
            this.data = data;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }
    }

}
